#include <vector>
#include <iostream>

#include "Utility.h"

using namespace std;

/**
 There are n apples with known weights. Your task is to divide the apples into two groups 
 so that the difference between the weights of the groups is minimal.

 ## Input
 The next line has n integers p1,p2,…,pn: the weight of each apple.
 [3, 2, 7, 4, 1]
 Divide into two parts
 group1: 2, 3, 4
 group2: 1, 7
 min: 1

 ## Output
 Print one integer: the minimum difference between the weights of the groups.
 */

/**
 * @brief 
 * 
 * @param n 当前苹果数量
 * @param m1 左边一堆苹果的重量
 * @param m2 右边一堆苹果的重量
 * @param total 苹果的总数量,
 * @param apples 每一个苹果的重量,
 * @return int 
 */
int divide_apples(int n, int m1, int m2, int total, vector<int> &apples) {
  // Solve
  if (n == total) {
    return abs(m1 - m2);
  }

  int l = divide_apples(n + 1, apples[n] + m1, m2, total, apples);
  int r = divide_apples(n + 1, m1, apples[n] + m2, total, apples);

  return min(l, r);
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<int> apples {3, 2, 7, 4, 1};
  cout<<divide_apples(0, 0, 0, 5, apples)<<endl;
  return 0;
}
